package main

import (
	"fmt"
)

var maxVal int    // 最大价值
var weights []int // 物品的重量
var values []int  // 物品的价值
var n int         // 物品数量
var capacity int  // 背包容量

func backtrack(index, curWeight, curValue int) {
	if index == n {
		if curValue > maxVal {
			maxVal = curValue
		}
		return
	}

	// 不选当前物品
	backtrack(index+1, curWeight, curValue)

	// 选当前物品（前提是背包容量足够）
	if curWeight+weights[index] <= capacity {
		backtrack(index+1, curWeight+weights[index], curValue+values[index])
	}
}

func main() {
	// 读取输入
	//fmt.Print("请输入物品数量：")
	//fmt.Scan(&n)
	//
	////n = 5
	//
	//weights = make([]int, n)
	//values = make([]int, n)
	//
	//fmt.Println("请输入每个物品的重量和价值：")
	//for i := 0; i < n; i++ {
	//	fmt.Scan(&weights[i], &values[i])
	//}
	//
	//fmt.Print("请输入背包的容量：")
	//fmt.Scan(&capacity)
	n = 5
	weights = []int{1, 2, 3, 4, 5}
	values = []int{2, 3, 4, 5, 6}
	capacity = 7
	// 初始化最大价值为0
	maxVal = 0

	// 回溯求解
	backtrack(0, 0, 0)

	// 输出结果
	fmt.Printf("背包能够装载的最大价值为：%d\n", maxVal)
}
